⟸ pàgina anterior ⟸

Exercici 5 (Tasca 7).

(P, NP, Kleene star)

Tancament per l’estrella de Kleene

1. Mostreu que \mathsf{P} és tancada per l’estrella de Kleene.

   Consell

   Utilitzeu programació dinàmica. Donat un conjunt A \in \mathsf{P} sobre \Sigma i una entrada x = x_1 \dots x_n amb x_i \in \Sigma, construïu una taula que indiqui per a cada i < j si el submot x_i \dots x_j és a A^*.

2. Mostreu que \mathsf{NP} és tancada per l’estrella de Kleene.